package sivak.net.proc.dyn.tree_lib;

/**
 * Created with IntelliJ IDEA.
 * User: ZefiR
 * Date: 23.01.13
 * Time: 22:45
 * To change this template use File | Settings | File Templates.
 */
public class BinaryTreeUtils {
    public static int size(TreeNode root) {
        if (root.left == null && root.right == null)
            return 1;
        else if (root.left == null)
            return 1 + size(root.right);
        else if (root.right == null)
            return 1 + size(root.left);
        return 1 + size(root.left) + size(root.right);
    }

    public static int height(TreeNode root) {
        if (root.left == null && root.right == null)
            return 1;
        if (root.left == null)
            return 1 + height(root.right);
        if (root.right == null)
            return 1 + height(root.left);
        int heightLeft = height(root.left);
        int heightRight = height(root.right);
        return heightLeft < heightRight ? heightRight + 1 : heightLeft + 1;
    }

    public static int sum(TreeNode root) {
        if (root.left == null && root.right == null)
            return root.value;
        if (root.left == null)
            return root.value + sum(root.right);
        if (root.right == null)
            return root.value + sum(root.left);
        return root.value + sum(root.left) + sum(root.right);
    }

    public static int max(TreeNode root) {
        if (root.left == null && root.right == null)
            return root.value;
        if (root.left == null)
            return Math.max(root.value, max(root.right));
        if (root.right == null)
            return Math.max(root.value, max(root.left));
        int maxLeft = max(root.left);
        int maxRight = max(root.right);
        return Math.max(root.value, Math.max(maxLeft, maxRight));
    }

}
